package com.ljm.boot.helloword.letCode;

public class Test239 {
    public static int[] maxSlidingWindow(int[] nums, int k) {

        int[] kk = new int[nums.length-k+1];
        int length = nums.length-k+1;

        for(int i=0;i<length;i++){
            int max = nums[i] ;
            for(int j=1; j<k;j++){
                if(max<=nums[i+j]){
                    max=nums[i+j];
                }
            }
            kk[i]=max;
            System.out.println(nums[i]);
        }
        return kk;

    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            }
            else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }

 public static int test(int[]  nums){
     int max = nums[0];
     int sum = 0;
     for (int num :nums) {
         sum = Math.max(sum + num,num);
         max = Math.max(sum,max);
     }
    return max;
 }

    public static void main(String[] args) {
        //System.out.println(Arrays.toString(maxSlidingWindow2(new int[]{1,3,-1,-3,5,3,6,7},3)));
        System.out.println(test(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
